// 给定一个整数数组nums和一个整数k
// 要求返回出现频率前k高的元素，可以按照任意顺序返回答案


// 思路1， 哈希表 + 优先队列

// 1. 使用哈希表记录下数组中各个元素的频数
// 2. 然后将哈希表中的元素去重，转换为新数组，时间复杂度为O(n),空间复杂度O(n)
// 3. 使用二叉堆构建优先队列，优先级为元素频数，此时堆顶元素即为频数最高的元素，时间复杂度为O(n)， 空间复杂度O(n)
// 4. 将堆顶元素加入到答案数组中，进行出队操作，时间复杂度为O(logn)
//    出队操作：交换堆顶元素和末尾元素，将末尾元素移出堆，继续调整大顶堆
// 5. 不断重复第4步，调整k次的时间复杂度O(nlogn)

function HeapQueue() {

}

HeapQueue.prototype.heappush = function (nums, nums_dict, value) {
    nums.push(value)
    let size = nums.length
    let i = size - 1
    while (Math.floor((i - 1) / 2) >= 0) {
        let curRoot = Math.floor((i - 1) / 2)
        if (nums_dict.get(nums[curRoot]) > nums_dict.get(value)) {
            break
        }
        nums[i] = nums[curRoot]
        i = curRoot
    }
    nums[i] = value
}

HeapQueue.prototype.heapAdjust = function (nums, nums_dict, index, end) {
    let left = index * 2 + 1
    let right = left + 1
    while (left <= end) {
        let max_index = index
        if (nums_dict.get(nums[left]) > nums_dict.get(nums[max_index])) {
            max_index = left
        }
        if (right <= end && nums_dict.get(nums[right]) > nums_dict.get(nums[max_index])) {
            max_index = right
        }
        if (index === max_index) {
            break
        }

        [nums[index], nums[max_index]] = [nums[max_index], nums[index]]
        // 继续调整子树
        index = max_index
        left = index * 2 + 1
        right = left + 1
    }
}

HeapQueue.prototype.heapify = function (nums, nums_dict) {
    let size = nums.length
    for (let i = Math.floor((size - 2) / 2); i >= 0; i--) {
        this.heapAdjust(nums, nums_dict, i, size - 1)
    }
}

HeapQueue.prototype.heappop = function (nums, nums_dict) {
    let size = nums.length;

    [nums[0], nums[size - 1]] = [nums[size - 1], nums[0]]
    let top = nums.pop()
    if (size > 0) {
        this.heapAdjust(nums, nums_dict, 0, size - 2)
    }
    return top
}

function topKFrequent(nums, k) {
    // 统计元素频数
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i])) {
            map.set(nums[i], map.get(nums[i]) + 1)
        } else {
            map.set(nums[i], 1)
        }
    }
    let newNums = [...new Set(nums)]
    let queue = []
    let heap = new HeapQueue()
    for (let i = 0; i < newNums.length; i++) {
        heap.heappush(queue, map, newNums[i])
    }
    // heap.heapify(nums, map)
    let res = []
    for (let i = 0; i < k; i++) {
        res.push(heap.heappop(newNums, map))
    }
    return res
}

let nums = [1, 1, 1, 2, 2, 3], k = 2
console.log(topKFrequent(nums, k))